package shuati;

import java.util.*;

/**
 * @author 23050
 * @version 1.0
 * @description: TODO
 * @date 2024/1/21 20:25
 */
public class Demo05<N> {





  /*  public static void main(String[] args) {
        HashMap<String,String> map = new HashMap<>();
        map.put("1","1");
        map.put("2","2");
        System.out.println(map.size());
    }*/


/*    public static void main(String[] args) {
        List<Object> arrayList = Collections.synchronizedList(new ArrayList<>());
        List<Object> linkedList = Collections.synchronizedList(new LinkedList<>());
    }*/









    /*private static int N = 1010;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n,V;
        n = in.nextInt();
        V = in.nextInt();
        int[] v = new int[N];
        int[] w = new int[N];
        int[][] dp = new int[N][N];
        for(int i = 1;i<=n;i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }


        for(int i = 1;i<=n;i++ ){
            for(int j = 0;j<=V;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=v[i]){
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);


        dp = new int[N][N];
        for(int j = 1;j<=V;j++){
            dp[0][j] = -1;
        }

        for(int i = 1;i<=n;i++ ){
            for(int j = 0;j<=V;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=v[i] && dp[i][j-v[i]]!=-1){
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }

        if(dp[n][V]==-1){
            System.out.println(0);
        }else{
            System.out.println(dp[n][V]);
        }




    }







*/








   /* public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int a:stones){
            sum+=a;
        }

        int m = sum/2;
        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i<=n;i++){
            for(int j = 0;j<=m;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=stones[i-1]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }

        return sum-2*dp[n][m];

    }
*/




   /* public static void main(String[] args) {
        int[][] a = new int[5][1];
    }

    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int a:nums){
            sum+=a;
        }
        int aim = (sum+target)/2;
        if(aim<0||(sum+target)%2==1){
            return 0;
        }

        int[][] dp = new int[n+1][aim+1];
        dp[0][0] = 1;
        for(int i = 1;i<=n;i++){
            for(int j = 0;j<=aim;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1]){
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][aim];
    }
*/









    //分割子集，转换问题
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int a:nums){
            sum+=a;
        }
        if (sum%2==1){
            return false;
        }
        int aim = sum/2;

        boolean[] dp = new boolean[aim+1];
        dp[0] = true;
        for(int i = 1;i<=n;i++){
            //优化空间时修改遍历顺序，从后往前
            for(int j = aim;j>=0;j--){
                if (j>=nums[i-1]){
                    dp[j] = dp[j] || dp[j-nums[i-1]];
                }
            }
        }

        return dp[aim];






    }






  /*  //背包问题
    public static int N = 1010;
    public static void main(String[] args) {
        int n,V;
        int[] v = new int[N],w = new int[N];
        int[][] dp = new int[N][N];
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        V = in.nextInt();

        for(int i = 1;i<=n;i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=V;j++){
                dp[i][j] = dp[i-1][j];
                if (j>=v[i]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }

        System.out.println(dp[n][V]);


        dp = new int[N][N];

        for(int j = 1;j<=V;j++){
            dp[0][j] = -1;
        }

        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=V;j++){
                dp[i][j] = dp[i-1][j];
                if (j>=v[i] && dp[i-1][j-v[i]]!=-1){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
                }
            }
        }

        System.out.println(dp[n][V]==-1?0:dp[n][V]);


    }*/








    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length,n = nums2.length;

        int[][] dp = new int[m+1][n+1];

        int ret = 0;
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if (nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
        }

        return ret;

    }












 /*   public static void main(String[] args) {
        int[] a1 = {70,39,25,40,7};
        int[] a2 = {52,20,67,5,31};
        System.out.println(findLength(a1, a2));
    }
    //最长重复子数组
    public static int findLength(int[] nums1, int[] nums2) {
        StringBuffer s1 = new StringBuffer();
        StringBuffer s2 = new StringBuffer();
        for (int a:nums1){
            s1.append(a);
        }
        for (int a:nums2){
            s2.append(a);
        }


        String ss1 = s1.toString();
        String ss2 = s2.toString();
        int m = s1.length();
        int n = s2.length();
        System.out.println(ss1);
        System.out.println(ss1);

        for(int i = m;i>=0;i--){
            for(int j = 0;j+i<=m;j++){
                System.out.println(ss1.substring(j,j+i));
                if (ss2.contains(ss1.substring(j, j+i))){
                    return i;
                }
            }
        }

        return 0;

    }




    public boolean isMatch(String ss, String pp) {
        int m = ss.length();
        int n = pp.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        ss = " "+ ss;
        pp=" "+pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        for(int j = 2;j<=n;j+=2){
            if (p[j] == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }


        for(int i = 1;i<=m;i++){
            for(int j =1;j<=n;j++){
                if (p[j] == '*'){
                    dp[i][j] = dp[i][j-2] || (p[j-1] == '.' || p[j-1]==s[i]) &&dp[i-1][j];
                }else{
                    dp[i][j] = (p[j] == '.' || p[j]==s[i]) && dp[i-1][j-1];
                }
            }
        }

        return dp[m][n];






    }
*/





/*    public boolean isMatch(String ss, String pp) {
        int m = ss.length()+1;
        int n = pp.length()+1;

        boolean[][] dp = new boolean[m+1][n+1];
        ss = ss+" ";
        pp = pp+" ";
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        dp[0][0] = true;
        for(int j = 2;j<=n;j+=2){
            if (p[j] == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if (p[j] == '*'){
                    dp[i][j] = dp[i][j-2] || (p[j-1]=='.' || p[j-1]==s[i]) && dp[i-1][j];
                }else{
                    dp[i][j] = (p[j]=='.' || p[j]==s[i]) && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];




    }*/


    //通配符
  /*  public boolean isMatch(String ss, String pp) {

        int m = ss.length();
        int n = pp.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        ss = " "+ss;
        pp = " "+pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        for(int j = 1;j<=n;j++){
            if (p[j]=='*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }

        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if (p[j] == '*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }else{
                    dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i-1][j-1];
                }
            }
        }

        return dp[m][n];
    }*/


/*    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m+1][n+1];

        for(int j = 0;j<=n;j++){
            dp[0][j] = 1;
        }

        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                dp[i][j] = dp[i][j-1];
                if (t.charAt(i-1) == s.charAt(j-1)){
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];


    }*/














    /*public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        int[][] dp = new int[m+1][n+1];

        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if (nums1[i] == nums2[i]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
*/

    /*public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        int[][] dp = new int[m+1][n+1];

        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if (text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }*/














    /*public int minInsertions(String s) {
        int n = s.length();

        int[][] dp = new int[n][n];

        for(int i = n-1;i>=0;i--){
            for(int j = i+1;j<n;j++){
                if (s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i][j-1],dp[i+1][j])+1;
                }
            }
        }
        return dp[0][n-1];


    }*/






/*    public int longestPalindromeSubseq(String s) {
        //1.创建dp表

        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i =n-1;i>=0;i--){
            dp[i][i] = 1;
            for(int j = i+1;j<n;j++){
                if (s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];



    }*/





   /* public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];

        for(int i = n-1;i>=0;i--){
            for(int j = i;j<n;j++){
                if (s.charAt(i) == s.charAt(j)){
                    isPal[i][j] = i+1<j ? isPal[i+1][j-1]:true;
                }
            }
        }

        int[] dp = new int[n];

        for(int i = 0;i<n;i++){
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i = 0;i<n;i++){
            if (isPal[0][i]){
                dp[i] = 0;
            }else{
                for(int j = 1;j<=i;j++){
                    if (isPal[j][i]){
                        dp[i] = Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }

        }

        return dp[n-1];


    }*/






/*    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for(int i = n-1;i>=0;i--){
            for(int j = i;j<n;j++){
                if (s.charAt(i) == s.charAt(j)){
                    if (i+1<j){
                        dp[i][j] = dp[i+1][j-1];
                    }else{
                        dp[i][j] = true;
                    }
                }
            }
        }

        for(int i = 1;i<n-1;i++){
            for(int j = i;j<n-1;j++){
                if (dp[0][i-1] && dp[i][j] && dp[j+1][n-1]){
                    return true;
                }
            }
        }

        return false;
    }*/





/*

    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        int x = 0;
        int y = 0;
        for(int i = n-1;i>=0;i++){
            for(int j = i+1;j<n;j++){
                if (s.charAt(i) == s.charAt(j)){
                    if (i+1<j){
                        dp[i][j] = dp[i+1][j];
                    }else{
                        dp[i][j] = true;
                    }
                }
                if(dp[i][j] == true && (y-x)<(j-i)){
                    x = i;
                    y = j;
                }
            }
        }
        return s.substring(x,y+1);


    }
*/






    /*public int countSubstrings(String s) {

        int n = s.length();
        int ret = 0;
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1;i>=0;i--){
            for(int j = i;j<n;j++){
                if (s.charAt(i) == s.charAt(j)){
                    dp[i][j] = i+1<j?dp[i+1][j-1]:true;
                }
                if (dp[i][j]==true){
                    ret++;
                }
            }
        }

        return ret;


    }*/








    /*public int numberOfArithmeticSlices(int[] nums) {
        Map<Long, List<Integer>> hash = new HashMap<>();
        int n = nums.length;

        //绑定元素
        for(int i = 0;i<n;i++){
            long tmp = (long)nums[i];
            if (!hash.containsKey(tmp)){
                hash.put(tmp,new ArrayList<Integer>());
            }
            hash.get(tmp).add(i);
        }

        int[][] dp = new int[n][n];

        int sum = 0;
        for(int j = 2;j<n;j++){//固定倒数第一个数
            for(int i = 1;i<j;i++){//枚举倒数第二个数
                long a = 2L*nums[i]-nums[j];
                if (hash.containsKey(a)){
                    for(int k:hash.get(a)){//k是数组的下标
                        if (k<i){
                            dp[i][j] += dp[k][i]+1;
                        }else{
                            break;
                        }
                    }
                }
                sum+=dp[i][j];
            }
        }
        return sum;
    }*/






   /* //最长等差数列
    public int longestArithSeqLength(int[] nums) {

        Map<Integer,Integer> hash = new HashMap<Integer, Integer>();
        hash.put(nums[0],0);
       //建表
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i = 0;i<n;i++){
            Arrays.fill(dp[i],2);
        }

        int ret = 2;
        for(int i = 1;i<n;i++){
            for(int j = i+1;j<n;j++){
                int a = 2*nums[i]-nums[j];
                if (hash.containsKey(a)){
                    dp[i][j]=dp[hash.get(a)][i]+1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
            hash.put(nums[i],i);
        }


        return ret;

    }*/

/*    public int lenLongestFibSubseq(int[] arr) {
        //优化：将数组中的元素+下标绑定，存到hash表里面
        Map<Integer,Integer> hash = new HashMap<Integer, Integer>();
        int n = arr.length;
        for(int i = 0;i<n;i++){
            hash.put(arr[i],i);
        }
        int[][] dp = new int[n][n];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                dp[i][j] = 2;
            }
        }

        int ret = 2;
        for(int j = 2;j<n;j++){
            for(int i = 1;i<j;i++){
                int a = arr[j]-arr[i];
                if (a<arr[i] && hash.containsKey(a)){
                    dp[i][j] = dp[hash.get(a)][i]+1;
                }
                ret = Math.max(ret,dp[i][j]);
            }
        }
        return ret<3?0:ret;

    }*/


   /* public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        System.out.println(longestFibSubseq(arr));
    }


    public static int longestFibSubseq(int[] arr) {
        // 创建一个哈希表，存储每个数字及其索引
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            index.put(arr[i], i);
        }

        // 创建一个二维数组，存储每个数字的最长斐波那契子序列的长度
        int[][] dp = new int[arr.length][arr.length];

        // 初始化二维数组
        for (int i = 0; i < arr.length; i++) {
            dp[i][i] = 1;
        }

        // 遍历数组
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                // 如果当前数字和前一个数字之和在数组中，则更新当前数字的最长斐波那契子序列的长度
                if (index.containsKey(arr[j] - arr[i]) && index.get(arr[j] - arr[i]) < i) {
                    dp[i][j] = dp[index.get(arr[j] - arr[i])][i] + 1;
                }
            }
        }

        // 返回最长斐波那契子序列的长度
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }



    public int longestSubsequence(int[] arr, int difference) {

        //在哈希表中做dp
        Map<Integer,Integer> hash = new HashMap<Integer, Integer>();

        int ret = 1;
        for(int a:arr){
            hash.put(a,hash.getOrDefault(a-difference,0)+1);
            ret = Math.max(ret,hash.get(a));
        }
        return ret;


    }*/




/*    public int findLongestChain(int[][] pairs) {
        //预处理 排序
        Arrays.sort(pairs,(a,b)->a[0]-b[0]);
        int n = pairs.length;
        int[] dp = new int[n];
        //初始化
        for(int i = 0;i<n;i++){
            dp[i] = 1;
        }

        int ret = 1;
        for(int i = 1;i<n;i++){
            for(int j = 0;j<i;j++){
                if (pairs[j][1]<pairs[i][0]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;

    }*/





/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }
    }
*/




/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            String n1 = in.nextLine();
            int n = Integer.parseInt(n1);
            String[] arr = new String[n];
            for(int i = 0;i<n;i++){
                arr[i] = in.nextLine();
//                System.out.println(arr[i]);
            }

            List<String> ret = Arrays.asList(arr);
            Collections.sort(ret);

            for(int i = 0;i<ret.size()-1;i++){
                if (ret.get(i+1).contains(ret.get(i))){
                    ret.remove(ret.get(i));
                    i--;
                }
            }

            for(String a:ret){
                System.out.println("mkdir -p "+a);
            }

            System.out.println();
        }
    }*/



    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String[] arr = new String[n];
        int i = 0;
        while (i<n){
            String str = in.nextLine();
            arr[i] = str;
            i++;
        }
        int max = 0;
        List<String> ret = new ArrayList<>();
        for(int j = 0;j<arr.length;j++){
            if ((arr[j].split(" ")[1]).equals("connect")){
                ret.add(arr[j]);
            }else if((arr[j].split(" ")[1]).equals("disconnect")){
                ret.remove(ret.indexOf(arr[j])+1);
            }
            max = Math.max(max, ret.size());
        }

        System.out.println(max);


    }*/




//    public static void main(String[] args) {
//        int[] arr = {1,1,1,2};
//        System.out.println(removeDuplicates(arr));
//    }
//
//    public static  int removeDuplicates(int[] nums) {
//        int k = nums.length;
//        for(int i = 0;i<k-1;i++){
//            if (nums[i] == nums[i+1]){
//                for(int j = i;j<k-1;j++){
//                    nums[j] = nums[j+1];
//                }
//                k--;
//                i--;
//            }
//        }
//        return k;
//    }



}
